package demo11;

public class Test {

    public static void main(String[] args) {
        int[] height = {1,8,6,2,5,4,8,3,7};
//        int[] height = {1,2,1};
        System.out.println(maxArea(height));
    }




    //用最繁琐的穷举法，每种组合都作比较
//    public static int maxArea(int[] height) {
//        //保存当前最大值
//        int max = 0;
//        //设置步长
//        int step = 1;
//        for (; step < height.length; step++) {
//            //每一次循环，步长+1
//            for (int i = 0; i+step < height.length; i++) {
//                if(height[i] >= height[i+step]){
//                    //右边为短板
//                    if(max < height[i+step]*step){
//                        //找到更大的值
//                        max = height[i+step]*step;
//                    }
//                }else if(height[i] < height[i+step]){
//                    //左边为短板
//                    if(max < height[i]*step){
//                        //找到更大的值
//                        max = height[i]*step;
//                    }
//                }
//            }
//        }
//        return max;
//    }


    /*
    优化算法思路，扫描每一个点，假设这个点就是两个隔板中的短板，其左右两边由外到内找，
    只要找到比自己高的，其面积一定比再往内的板子面积要大，
    因为面积的高取决于短板，而面积的长取决于两点的距离
    如果扫描的过程，一直找不到比自己长的板，此循环不可能找到最大值！
    而如果找到比自己长的板，那就没有必要再往里扫描了，记录当前的面积是否比最大面积大，判断完就跳出循环
     */

    public static int maxArea(int[] height) {
        //保存当前最大值
        int max = 0;
        for (int i = 0; i < height.length; i++) {
            //扫描整个数组，分别对每个数都假设他们是最大面积中的那个短板

            //从左往右扫描到下标处
            for (int j = 0; j < i && height[i]*(i-j)>max; j++) {
                /*
                    height[i]*(i-j)>max的作用是，我们已经确定当前最小板是谁了
                    高已经确定，那长就是i-j，如果他们的积比max要小，
                    不管怎么扫描都不会找到更大的面积了，所以提前结束循环
                 */

                if(height[j]>=height[i]){
                    //找到了比当前短板要长的板
                    max = height[i]*(i-j);
                }
            }
            //从右往左扫描到下标处
            for (int j = height.length-1; j > i && height[i]*(j-i)>max; j--) {
                /*
                    height[i]*(j-i)>max的作用是，我们已经确定当前最小板是谁了
                    高已经确定，那长就是j-i，如果他们的积比max要小，
                    不管怎么扫描都不会找到更大的面积了，所以提前结束循环
                 */

                if(height[j]>=height[i]){
                    //找到了比当前短板要长的板
                    max = height[i]*(j-i);
                }
            }
        }
        return max;
    }
}
